package main

import (
	"bufio"
	"container/heap"
	"context"
	"encoding/json"
	"fmt"
	"io/fs"
	"log"
	"math"
	"math/rand"
	"os"
	"path/filepath"
	"regexp"
	"runtime"
	"sort"
	"strconv"
	"strings"
	"sync"
	"sync/atomic"
	"time"
)

func a() {
	//runtime.GOMAXPROCS(1)
	//wg := sync.WaitGroup{}
	//wg.Add(10)
	//for i := 0; i < 10; i++ {
	//	go func(i int) {
	//		fmt.Println("i: ", i)
	//		wg.Done()
	//	}(i)
	//}
	//wg.Wait()

	//ch := make(chan int)
	//count := 0
	//go func() {
	//	ch <- 1
	//}()
	//go func() {
	//	count++
	//}()
	//fmt.Println(count, <-ch) // 1 1
	//close(ch)

	//var wg sync.WaitGroup
	//wg.Add(2)
	//var ints = make([]int, 0)
	//go func() {
	//	for i := 0; i < 5; i++ {
	//		ints = append(ints, i)
	//	}
	//	wg.Done()
	//}()
	//go func() {
	//	for i := 0; i < 5; i++ {
	//		ints = append(ints, i)
	//	}
	//	wg.Done()
	//}()
	//wg.Wait()
	//fmt.Println(len(ints))
}

// 内存限制 默认10M
const memorySize = 10

func main() {
	//a()
	// 链表是否有环
	head := &ListNode{Val: 0}
	head1 := &ListNode{Val: 1}
	head.Next = head1
	head1.Next = head
	log.Print(IsCycle(head))
}

// file todo: 规定内存中处理大文件，归并待优化成最小堆
func file() {
	inputFile := "a.txt"
	outputFile := "b.txt"
	splitFiles, err := splitFile(inputFile)
	if err != nil {
		log.Print(err)
		return
	}
	err = mergeFile(splitFiles, outputFile)
	if err != nil {
		log.Print(err)
		return
	}
}

func mergeFile(splitFiles []string, outputFile string) error {
	// 创建输出文件
	outputtedFile, err := os.Create(outputFile)
	defer outputtedFile.Close()
	if err != nil {
		return err
	}
	writer := bufio.NewWriter(outputtedFile)

	// 给每个文件创建一个扫描器
	l := len(splitFiles)
	files := make([]*os.File, l)
	scanners := make([]*bufio.Scanner, l)
	for i, splitFile := range splitFiles {
		file, err := os.Open(splitFile)
		if err != nil {
			return err
		}
		files[i] = file
		scanners[i] = bufio.NewScanner(file)
		if !scanners[i].Scan() {
			scanners[i] = nil
		}
	}

	// 归并排序
	for {
		minIndex := -1
		for i, scanner := range scanners {
			if scanner != nil {
				if minIndex == -1 || scanner.Text() < scanners[minIndex].Text() {
					minIndex = i
				}
			}
		}
		if minIndex == -1 {
			break
		}
		_, err = writer.WriteString(scanners[minIndex].Text() + "\n")
		if err != nil {
			return err
		}
		if !scanners[minIndex].Scan() {
			scanners[minIndex] = nil
		}
	}

	err = writer.Flush()
	if err != nil {
		return err
	}

	// 关闭文件
	for _, file := range files {
		err := file.Close()
		if err != nil {
			return err
		}
	}

	// 删除临时文件
	for _, file := range splitFiles {
		err := os.Remove(file)
		if err != nil {
			return err
		}
	}
	return nil
}

func splitFile(inputFile string) ([]string, error) {
	var chunkFiles []string
	openFile, err := os.Open(inputFile)
	defer openFile.Close()
	if err != nil {
		return chunkFiles, err
	}
	var currentChunk []string
	chunkIndex := 0
	currentSize := 0
	scanner := bufio.NewScanner(openFile)
	for scanner.Scan() {
		line := scanner.Text()
		currentChunk = append(currentChunk, line)
		currentSize += len(line) + 1
		// 内存不满足时写入临时文件
		if currentSize > memorySize {
			sort.Strings(currentChunk)
			chunkFile, err := writeChunkToFile(currentChunk, chunkIndex)
			if err != nil {
				return chunkFiles, err
			}
			chunkFiles = append(chunkFiles, chunkFile)
			currentChunk = nil
			currentSize = 0
			chunkIndex++
		}
	}

	// 最后一块
	if len(currentChunk) > 0 {
		sort.Strings(currentChunk)
		lastChunkFile, err := writeChunkToFile(currentChunk, chunkIndex)
		if err != nil {
			return chunkFiles, nil
		}
		chunkFiles = append(chunkFiles, lastChunkFile)
	}
	return chunkFiles, nil
}

func writeChunkToFile(chunk []string, index int) (string, error) {
	fileName := "chunk_" + strconv.Itoa(index) + ".txt"
	file, err := os.Create(fileName)
	defer file.Close()
	if err != nil {
		return "", err
	}
	writer := bufio.NewWriter(file)
	for _, v := range chunk {
		_, err := writer.WriteString(v + "\n")
		if err != nil {
			return "", err
		}
	}
	err = writer.Flush()
	if err != nil {
		return "", err
	}
	return fileName, nil
}

// CoinChangeProblem todo: 零钱兑换问题
func CoinChangeProblem() {
	s := []int{1, 2, 5}
	target := 11
	var (
		path = make([]int, target+1)
		dp   = make([]int, target+1)
	)
	for i := 1; i <= target; i++ {
		dp[i] = math.MaxInt32
		for _, coin := range s {
			if i >= coin && dp[i-coin] != math.MaxInt32 && dp[i-coin]+1 < dp[i] {
				dp[i] = dp[i-coin] + 1
				path[i] = coin
			}
		}
	}
	if dp[target] == math.MaxInt32 {
		log.Print(dp)
		return
	}
	var res []int
	for target > 0 {
		res = append(res, path[target])
		target -= path[target]
	}
	log.Print(res, 11)
}

type ListNode struct {
	Val  int
	Next *ListNode
}

// IsCycle 链表是否有环 环形链表
func IsCycle(head *ListNode) (*ListNode, bool) {
	if head == nil || head.Next == nil {
		return nil, false
	}
	slow := head
	fast := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			slow = head
			for slow != fast {
				slow = slow.Next
				fast = fast.Next
			}
			return slow, true
		}
	}
	return nil, false
}

// List todo: 反转链表
type List struct {
	Val  int
	Next *List
}

func reversalList(root *List) *List {
	var preList *List
	head := root
	for head != nil {
		next := head.Next
		head.Next = preList
		preList = head
		head = next
	}
	return preList
}

func PrintList(head *List) {
	for head != nil {
		fmt.Printf("%d->", head.Val)
		head = head.Next
	}
}

func doReversalList() {
	head := &List{
		Val: 1,
		Next: &List{
			Val:  2,
			Next: nil,
		},
	}
	reversal := reversalList(head)
	PrintList(reversal)
}

// everySeconds todo: 规定时间内每秒recover一次
func everySeconds() {
	// 请在这里填写代码
	ctx, cancel := context.WithTimeout(context.Background(), time.Second*10)
	defer cancel()
	tiker := time.NewTicker(time.Second)
	defer tiker.Stop()
	for {
		select {
		case <-ctx.Done():
			fmt.Println("quit")
			return
		case <-tiker.C:
			go func() {
				defer func() {
					if r := recover(); r != nil {
						fmt.Println(r)
					}
				}()
				proc := func() {
					panic("ok")
				}
				proc()
			}()
		}
	}
}

// ReentrantLock todo: ReentrantLock 可重入锁
type ReentrantLock struct {
	owner     int64
	recursion int32
	mu        sync.Mutex
}

// 获取当前 Goroutine ID
func getGoroutineId() int64 {
	var buf [64]byte
	n := runtime.Stack(buf[:], false)
	stack := string(buf[:n])
	var gid int64
	_, err := fmt.Sscanf(stack, "goroutine %d ", &gid)
	if err != nil {
		panic(0)
	}
	log.Print(gid)
	return gid
}

func (r *ReentrantLock) Lock() {
	gid := getGoroutineId()

	if atomic.LoadInt64(&r.owner) == gid {
		// 如果当前 Goroutine 已经持有锁，递增重入计数
		r.recursion++
		return
	}

	r.mu.Lock()
	atomic.StoreInt64(&r.owner, gid)
	r.recursion = 1
}

func (r *ReentrantLock) Unlock() {
	gid := getGoroutineId()

	if atomic.LoadInt64(&r.owner) != gid {
		// 如果当前 Goroutine 不持有锁，不能解锁
		panic("attempt to unlock a lock held by another goroutine")
	}

	r.recursion--
	if r.recursion == 0 {
		atomic.StoreInt64(&r.owner, -1)
		r.mu.Unlock()
	}
}

// Node todo: 表存多叉树，寻找根节点到子节点的路径
type Node struct {
	ID  string
	PID string
}

func buildPaths(nodes []*Node) {
	nodesMap := make(map[string]string)
	for _, node := range nodes {
		nodesMap[node.ID] = node.PID
	}
	path := make([]string, 0, len(nodes))
	for _, node := range nodes {
		path = append(path, buildPath(node.ID, nodesMap))
	}
}

func buildPath(id string, nodesMap map[string]string) string {
	if nodesMap[id] == "-1" {
		return fmt.Sprintf("/%s", id)
	}
	return fmt.Sprintf("%s/%s", buildPath(nodesMap[id], nodesMap), id)
}

// Node2 todo: 递归构建层接结构
type Node2 struct {
	ID       string
	PID      string
	Children []*Node2
}

func buildTree(pid string, nodes []*Node) []*Node2 {
	children := make([]*Node2, 0)
	for _, node := range nodes {
		if node.PID == pid {
			child := &Node2{
				ID:       node.ID,
				PID:      node.PID,
				Children: buildTree(node.ID, nodes),
			}
			children = append(children, child)
		}
	}
	return children
}

func doBuildTree() {
	node1 := []*Node{
		{"A", "-1"},
		{"A-1", "A"},
		{"A-2", "A"},
		{"A-3", "A"},
		{"A-2-1", "A-2"},
		{"A-2-2", "A-2"},
		{"A-2-3", "A-2"},
		{"B", "-1"},
		{"B-1", "B"},
		{"B-1-1", "B-1"},
	}

	buildPaths(node1)
	res := buildTree("-1", node1)
	b, _ := json.Marshal(res)
	log.Print(string(b))
	//node2 := []Node2{
	//	{
	//		ID:  "A",
	//		PID: "-1",
	//		Children: []*Node2{
	//			{
	//				ID:       "A-1",
	//				PID:      "A",
	//				Children: nil,
	//			},
	//			{
	//				ID:  "A-2",
	//				PID: "A",
	//				Children: []*Node2{
	//					{
	//						ID:       "A-2-1",
	//						PID:      "A-2",
	//						Children: nil,
	//					},
	//					{
	//						ID:       "A-2-2",
	//						PID:      "A-2",
	//						Children: nil,
	//					},
	//					{
	//						ID:       "A-2-3",
	//						PID:      "A-2",
	//						Children: nil,
	//					},
	//				},
	//			},
	//			{
	//				ID:       "A-1",
	//				PID:      "A",
	//				Children: nil,
	//			},
	//		},
	//	},
	//}
}

// TreeNode todo 层级遍历二叉树
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func traverseBinaryTreeByLevel(root *TreeNode, level int, levels *[][]int) {
	if root == nil {
		return
	}
	if len(*levels) == level {
		*levels = append(*levels, []int{})
	}
	(*levels)[level] = append((*levels)[level], root.Val)
	log.Print(root.Val)
	traverseBinaryTreeByLevel(root.Left, level+1, levels)
	traverseBinaryTreeByLevel(root.Right, level+1, levels)
}

func doTraverseBinaryTreeByLevel() {
	var (
		tree = &TreeNode{
			Val: 1,
			Left: &TreeNode{
				Val: 2,
				Left: &TreeNode{
					Val: 4,
				},
				Right: &TreeNode{
					Val: 5,
				},
			},
			Right: &TreeNode{
				Val: 3,
				Left: &TreeNode{
					Val: 6,
				},
				Right: &TreeNode{
					Val: 7,
				},
			},
		}
		levels [][]int
	)
	traverseBinaryTreeByLevel(tree, 0, &levels)
	log.Print(1)
}

// minPath2 todo：从第一行任意位置到最后一行任意位置的最小和
func minPath2(g [][]int) int {
	var res int
	for _, v := range g {
		sort.Ints(v)
		res += v[0]
	}
	return res
}

// find todo: 找b在a出现的位置 a=[]int{1,2,3,4} b=[]int{1,2}
func find(a, b []int) []int {
	var (
		res []int
		m   = make(map[int]struct{})
	)
	for _, v := range b {
		m[v] = struct{}{}
	}
	for i, v := range a {
		if _, ok := m[v]; ok {
			res = append(res, i)
		}
	}
	return res
}

func doMinPath() {
	matrix := [][]int{
		{5, 8, 1, 2},
		{4, 1, 7, 3},
		{3, 6, 2, 9},
	}

	//fmt.Println(minPath(matrix))
	t := minPath2(matrix)
	fmt.Println(t)
}

// minPath todo：在矩阵左上角到右下角最小的和
func minPath(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	//左上角
	dp[0][0] = grid[0][0]
	//初始化第一行
	for i := 1; i < n; i++ {
		dp[0][i] = dp[0][i-1] + grid[0][i]
	}
	//初始化第一列
	for i := 1; i < m; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = grid[i][j] + int(math.Min(float64(dp[i-1][j]), float64(dp[i][j-1])))
		}
	}
	return dp[m-1][n-1]
}

// isSieve todo: 返回小于整数n的所有质数
func isSieve(n int) (bool, []int) {
	if n < 2 {
		return false, nil
	}
	s := make([]bool, n+1)
	for i := 2; i < n; i++ {
		s[i] = true
	}

	p := int(math.Sqrt(float64(n)))
	for i := 2; i <= p; i++ {
		if s[i] {
			for j := i * i; j <= n; j += i {
				s[j] = false
			}
		}
	}
	var res []int
	for i := range s {
		if s[i] {
			res = append(res, i)
		}
	}
	return true, res
}
func sieve(n int) []int {
	if n < 2 {
		return []int{}
	}
	isPrime := make([]bool, n+1)
	for i := 2; i < n; i++ {
		isPrime[i] = true
	}
	limit := int(math.Sqrt(float64(n)))
	for i := 2; i <= limit; i++ {
		if isPrime[i] {
			for j := i * i; j <= n; j += i {
				isPrime[j] = false
			}
		}
	}
	primes := []int{}
	for i := 2; i <= n; i++ {
		if isPrime[i] {
			primes = append(primes, i)
		}
	}
	return primes
}

// findMinColumns todo:找到每一列的最小值
func findMinColumns(m [][]int) []int {
	if len(m) == 0 {
		return []int{}
	}
	numRows := len(m)
	numCols := len(m[0])
	minValues := make([]int, numCols)
	for i := range minValues {
		minValues[i] = math.MaxInt
	}
	for col := 0; col < numCols; col++ {
		for row := 0; row < numRows; row++ {
			if m[row][col] < minValues[col] {
				minValues[col] = m[row][col]
			}
		}
	}
	return minValues
}

// findMinRows todo:找到每一行的最小值
func findMinRows(m [][]int) []int {
	if len(m) == 0 {
		return []int{}
	}
	numRows := len(m)
	numCols := len(m[0])
	minValues := make([]int, numRows)
	for i := range minValues {
		minValues[i] = math.MaxInt
	}
	for row := 0; row < numRows; row++ {
		for col := 0; col < numCols; col++ {
			if m[row][col] < minValues[row] {
				minValues[row] = m[row][col]
			}
		}
	}
	return minValues
}

// sortVersion todo:归并排序 升序版本号
func sortVersion() {
	s := []string{
		"1.23",
		"2.11",
		"1.8",
		"2.8",
	}
	m := make([][]int, 0, len(s))
	r := make([][]int, 0, len(s))
	for _, v := range s {
		ss := strings.Split(v, ".")
		var tmp []int
		for _, v := range ss {
			vv, _ := strconv.Atoi(v)
			tmp = append(tmp, vv)
		}
		m = append(m, tmp)
	}
	for {
		min := math.MinInt32
		for i, v := range m {
			if len(m) > 0 {
				if (min == math.MinInt32 || m[min][0] > v[0]) || (m[min][0] == v[0] && m[min][1] > v[1]) {
					min = i
				}
			}
		}
		if min == math.MinInt32 {
			break
		}
		r = append(r, m[min])
		m = append(m[0:min], m[min+1:]...)
	}
}

// candy todo:给一排孩子分发糖果
func candy() {
	s := []int{1, 0, 3}
	m := make([]int, len(s))
	for i := 0; i < len(m); i++ {
		m[i] = 1
	}
	for i := 1; i < len(s); i++ {
		if s[i] > s[i-1] {
			m[i] = m[i-1] + 1
		}
	}
	for i := len(s) - 2; i >= 0; i-- {
		if s[i] > s[i+1] {
			m[i] = max(m[i], m[i+1]+1)
		}
	}
	sum := 0
	for _, v := range m {
		sum += v
	}
	log.Print(sum)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// productExceptSelf todo:除自身外所有数的乘积
func productExceptSelf() {
	s := []int{1, 2, 3, 4}
	n := len(s)
	r := make([]int, n)

	left := 1
	for i := 0; i < n; i++ {
		r[i] = left
		left *= s[i]
	} // 1 1 2 6

	right := 1
	for i := n - 1; i >= 0; i-- {
		r[i] *= right
		right *= s[i]
	} //6 8 12 24
}

// maxCount todo:打家劫舍问题，只能拿相邻元素中的一个，使得数组所有元素和最大
func maxCount(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
	dp := make([]int, n)
	dp[0] = nums[0]
	dp[1] = max(dp[0], nums[1])
	for i := 2; i < n; i++ {
		dp[i] = max(dp[i-1], dp[i-2]+nums[i])
	}
	return dp[n-1]
}

// sliceReversalList todo: 切片转换成链表
func sliceReversalList(s []int) *ListNode {
	if len(s) <= 0 {
		return nil
	}
	head := &ListNode{Val: s[0]}
	current := head
	for _, v := range s[1:] {
		current.Next = &ListNode{Val: v}
		current = current.Next
	}
	return head
}

// MinHeap todo：最小堆寻找topK元素
type MinHeap struct {
	data []int
	size int
}

func newMinHeap(k int) *MinHeap {
	return &MinHeap{
		data: make([]int, 0, k),
		size: 0,
	}
}

func (h *MinHeap) insert(val int) {
	if h.size < cap(h.data) {
		h.data = append(h.data, val)
		h.size++
		h.up(h.size - 1)
	} else if val > h.data[0] {
		h.data[0] = val
		h.down(0)
	}
}

func (h *MinHeap) up(index int) {
	parent := (index - 1) / 2
	for index > 0 && h.data[parent] > h.data[index] {
		h.data[parent], h.data[index] = h.data[index], h.data[parent]
		index = parent
		parent = (index - 1) / 2
	}
}

func (h *MinHeap) down(index int) {
	small := index
	left := 2*index + 1
	right := 2*index + 2
	if left < h.size && h.data[left] < h.data[small] {
		small = left
	}
	if right < h.size && h.data[right] < h.data[small] {
		small = right
	}

	if small != index {
		h.data[small], h.data[index] = h.data[index], h.data[small]
		h.down(small)
	}
}

func (h *MinHeap) top() int {
	if h.size == 0 {
		return -1
	}
	return h.data[0]
}

func findK(nums []int, k int) {
	minHeap := newMinHeap(k)
	for i := 0; i < k; i++ {
		minHeap.insert(nums[i])
	}

	for i := k; i < len(nums); i++ {
		if minHeap.top() < nums[i] {
			minHeap.insert(nums[i])
		}
	}
	log.Print(minHeap.top())
}

// minHeap todo：最小堆寻找topK元素-用heap接口实现
type minHeap []int

func (h *minHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *minHeap) Len() int {
	return len(*h)
}

func (h *minHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j]
}

func (h *minHeap) Push(val any) {
	*h = append(*h, val.(int))
}

func (h *minHeap) Pop() any {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[0 : n-1]
	return x
}

func findKOfHeapInterface() {
	nums := []int{1, 2, 3, 84, 9, 2, 998, 23}
	k := 2
	h := &minHeap{}
	heap.Init(h)
	for _, v := range nums {
		if h.Len() < k {
			heap.Push(h, v)
		} else if v > (*h)[0] {
			(*h)[0] = v
			heap.Fix(h, 0)
		}
	}
	res := make([]int, h.Len())
	for i := 0; h.Len() > 0; i++ {
		res[i] = heap.Pop(h).(int)
	}
	log.Print(res)
}

type list struct {
	val  int
	next *list
}

// deleteMiddleList todo:删除链表中间节点
func deleteMiddleList(head *list) *list {
	if head == nil || head.next == nil {
		return nil
	}
	var l int
	for i := head; i != nil; i = i.next {
		l++
	}
	m := l / 2
	if m == 0 {
		return nil
	}
	//one:找到中间节点的前一个节点
	//current := head
	//for i := 0; i < m-1; i++ {
	//	current = current.next
	//}
	//current.next = current.next.next

	//two:返回一个新链表,循环链表跳过中间节点
	newList := &list{val: head.val}
	current := newList
	for i := 0; i < l-1; i++ {
		head = head.next
		if i == m-1 {
			continue
		}
		current.next = &list{val: head.val}
		current = current.next
	}
	head = newList
	return head
}

func sliceToList(s []int) *list {
	if len(s) == 0 {
		return nil
	}
	head := &list{val: s[0]}
	current := head
	for _, v := range s[1:] {
		current.next = &list{val: v}
		current = current.next
	}
	return head
}

// oddEven todo :奇偶链表：把单链表里的节点变成奇数在前偶数在后的新链表，奇数指针把奇数放在一起，偶数指针把偶数放在一起，
// 最后合并奇偶两个链表
func oddEven(head *list) {
	if head == nil || head.next == nil {
		return
	}
	odd := head
	even := head.next
	evenHead := even
	for even != nil && even.next != nil {
		odd.next = even.next
		odd = odd.next
		even.next = odd.next
		even = even.next
	}
	odd.next = evenHead
}

func doOddEven() {
	l := sliceToList([]int{1, 2, 3, 4, 5, 6})
	oddEven(l)
}

// sqrt todo:自定义平方根函数
func sqrt(n int) int {
	if n < 0 {
		panic("输入必须是非负整数")
	}

	if n == 0 || n == 1 {
		return n
	}

	x := n
	y := (x + n/x) / 2

	for y < x {
		x = y
		y = (x + n/x) / 2
	}

	return x
}

// deleteRepeatNum todo 删除重复元素
func deleteRepeatNum() {
	s := []int{1, 1, 2, 2, 3, 3, 4}
	i := 0
	for j := 1; j < len(s); j++ {
		if s[j] != s[i] {
			i++
			s[i] = s[j]
		}
	}
}

// deleteTargetValue todo：删除指定元素
func deleteTargetValue(s []int, target int) []int {
	l := len(s)
	if l == 0 {
		return []int{}
	}
	i := 0
	for j := 0; j < l; j++ {
		if s[j] != target {
			s[i] = s[j]
			i++
		}
	}
	log.Print(i)
	return s[0:i]
}

// deleteRepeatTow 删除重复超过2个元素的超过部分
func deleteRepeatTow() {
	s := []int{1, 1, 2, 3}
	i := 2
	for j := 2; j < len(s); j++ {
		if s[j] != s[i-2] {
			s[i] = s[j]
			i++
		}
	}
	log.Print(s[:i])
}

// eggDrop todo:鸡蛋跳楼动 傻逼态规划解法
func eggDrop(eggs, floors int) int {
	dp := make([][]int, eggs+1)
	for i := range dp {
		dp[i] = make([]int, floors+1)
	}

	// 初始化：如果只有1个鸡蛋，那么需要逐层试探
	for j := 1; j <= floors; j++ {
		dp[1][j] = j
	}

	for i := 2; i <= eggs; i++ {
		for j := 1; j <= floors; j++ {
			dp[i][j] = math.MaxInt32
			for x := 1; x <= j; x++ {
				res := 1 + max(dp[i-1][x-1], dp[i][j-x])
				if res < dp[i][j] {
					dp[i][j] = res
				}
			}
		}
	}

	return dp[eggs][floors]
}

// reverseBetween TODO 反转链表中从 l 到 r 的部分
func reverseBetween(head *ListNode, l int, r int) *ListNode {
	if head == nil || l == r {
		return head
	}

	dummy := &ListNode{Next: head}
	prev := dummy

	// 找到第 l 个节点的前一个节点
	for i := 1; i < l; i++ {
		prev = prev.Next
	}

	// 开始反转链表
	current := prev.Next
	var next *ListNode
	for i := 0; i < r-l; i++ {
		next = current.Next
		current.Next = next.Next
		next.Next = prev.Next
		prev.Next = next
	}
	return dummy.Next
}

// subjects todo:找到数组元素的子集(去重复)
func subjects(s []int) [][]int {
	var result [][]int
	var current []int
	sort.Ints(s)
	var backtrack func(int)
	backtrack = func(start int) {
		tmp := make([]int, len(current))
		copy(tmp, current)
		result = append(result, tmp)
		for i := start; i < len(s); i++ {
			if i > start && s[i] == s[i-1] {
				continue
			}
			current = append(current, s[i])
			backtrack(i + 1)
			current = current[:len(current)-1]
		}
	}
	backtrack(0)
	return result
}

// Prize todo 奖品和对应的权重
type Prize struct {
	Name   string
	Weight int
}

// drawWeighted todo: 构建累积和数组，并通过二分查找确定中奖奖品
func drawWeighted(prizes *[]Prize) string {
	if len(*prizes) == 0 {
		return ""
	}
	// 构建前缀和数组
	prefixSums := make([]int, len(*prizes))
	prefixSums[0] = (*prizes)[0].Weight
	for i := 1; i < len(*prizes); i++ {
		prefixSums[i] = prefixSums[i-1] + (*prizes)[i].Weight
	}

	// 生成一个随机数，范围是 [1, totalWeight]，避免 randomWeight 为 0 的情况
	rand.Seed(time.Now().UnixNano())
	totalWeight := prefixSums[len(prefixSums)-1]
	randomWeight := rand.Intn(totalWeight) + 1 // [1, totalWeight]
	randomWeight = 2
	// 使用二分查找在前缀和数组中定位中奖奖品
	index := sort.Search(len(prefixSums), func(i int) bool {
		log.Print(prefixSums[i])
		return prefixSums[i] >= randomWeight
	})

	// 获取中奖的奖品
	winner := (*prizes)[index].Name

	// 将中奖的奖品从列表中移除
	*prizes = append((*prizes)[:index], (*prizes)[index+1:]...)

	return winner
}

// maxPathSum 矩阵从左上角到右下角的最小路径和 第二种写法
func maxPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}

	m, n := len(grid), len(grid[0])
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = grid[i][j]
			} else if i == 0 {
				dp[i][j] = dp[i][j-1] + grid[i][j]
			} else if j == 0 {
				dp[i][j] = dp[i-1][j] + grid[i][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
			}
		}
	}
	return dp[m-1][n-1]
}

// findMinSumPath 矩阵从左上角到右下角的最小路径和
func findMinSumPath(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if m == 0 || n == 0 {
		return -1
	}
	// 初始化第一行的路径和
	for j := 1; j < n; j++ {
		grid[0][j] += grid[0][j-1]
	}
	//初始化第一列路径和
	for i := 1; i < m; i++ {
		grid[i][0] += grid[i-1][0]
	}
	// 填充其他位置
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			grid[i][j] += getMin(grid[i-1][j], grid[i][j-1])
		}
	}
	return grid[m-1][n-1]
}

func getMin(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// fallingMinSum 从第一行任意位置到最后一行任意位置的最短路径和
func fallingMinSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if m == 0 || n == 0 {
		return -1
	}
	for i := 1; i < m; i++ {
		for j := 0; j < n; j++ {
			//正上方
			minTmp := grid[i-1][j]
			//左上方
			if j > 0 {
				minTmp = getMin(minTmp, grid[i-1][j-1])
			}
			//右上方
			if j < n-1 {
				minTmp = getMin(minTmp, grid[i-1][j+1])
			}
			grid[i][j] += minTmp
		}
	}
	// 找到最后一行最小元素
	res := math.MaxInt32
	for _, v := range grid[m-1] {
		res = getMin(res, v)
	}
	return res
}

const gNum = 10

func isValidFile(path string) bool {

	info, err := os.Stat(path)
	if err != nil {
		return false
	}
	return info.Size() < 1024*1024
}

// scanConcurrently 一种写法
func scanConcurrentlyOne(root string) []string {
	var wg sync.WaitGroup
	var l sync.Mutex
	var res []string
	fileCh := make(chan string)
	for i := 0; i < gNum; i++ {
		go func() {
			for file := range fileCh {
				if isValidFile(file) {
					l.Lock()
					res = append(res, file)
					l.Unlock()
				} else {
					fmt.Printf("%s不满足", file)
				}
				wg.Done()
			}

		}()
	}
	err := filepath.WalkDir(root, func(path string, d fs.DirEntry, err error) error {
		if err != nil {
			return err
		}
		wg.Add(1)
		fileCh <- path
		return nil
	})
	if err != nil {
		fmt.Printf("%v", err)
	}
	// todo:思考：fileCH会不会出现被关闭前，还没接收完？不会
	//close(fileCh)
	wg.Wait()
	return res
}

// scanConcurrently 第二种写法
func scanConcurrentlyTwo(root string) []string {
	var wg sync.WaitGroup
	var l sync.Mutex
	var res []string
	fileCh := make(chan string)
	for i := 0; i < gNum; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			//time.Sleep(time.Second)
			for file := range fileCh {
				if isValidFile(file) {
					l.Lock()
					res = append(res, file)
					l.Unlock()
				} else {
					fmt.Printf("%s不满足", file)
				}
			}
		}()
	}
	err := filepath.WalkDir(root, func(path string, d fs.DirEntry, err error) error {
		if err != nil {
			return err
		}
		fileCh <- path
		return nil
	})
	if err != nil {
		fmt.Printf("%v", err)
	}
	// todo:思考：fileCH会不会出现被关闭前，还没接收完？不会
	close(fileCh)
	wg.Wait()
	return res
}

// 并发获取目录下满足条件的 文件和目录
func do() {
	ch := make(chan int)
	wg := sync.WaitGroup{}
	for i := 0; i < 10; i++ {
		// todo 1: 而是第这里
		// wg.Add(1)
		go func() {
			// defer wg.Done()
			for {
				if n, ok := <-ch; ok {
					log.Print(n)
				}
				wg.Done()
			}
		}()
	}
	// todo :如果add不写在这里，而是1那里，则需要关闭channel为啥？
	wg.Add(5)
	ch <- 1
	ch <- 1
	ch <- 1
	ch <- 1
	ch <- 1
	//todo ????
	//close(ch)
	wg.Wait()
	scanConcurrentlyTwo("/Users/itianyu/workerSpace/studySpace/interface/interface/qustion")
}

type listT interface {
	~int | ~string
}

// topRepeatK 在一组单词中按重复出现降序排序的前k个单词，次数相同按元素本身排序
func topRepeatK[T listT](words []T, k int) []T {
	m := make(map[T]int)
	for _, word := range words {
		m[word]++
	}
	s := make([]T, 0, len(m))
	for v := range m {
		s = append(s, v)
	}
	sort.Slice(s, func(i, j int) bool {
		if m[s[i]] == m[s[j]] {
			return s[i] < s[j]
		}
		return m[s[i]] > m[s[j]]
	})
	return s[:k]
}

// findTopThree 寻找top3的三个数
func findTopThree(s []int, k int) (int, int, int) {
	first, second, third := math.MinInt32, math.MinInt32, math.MinInt32
	for _, v := range s {
		if v > first {
			third = second
			second = first
			first = v
		} else if v > second {
			third = second
			second = v
		} else if v > third {
			third = v
		}
	}
	return first, second, third
}

func doTask(ctx context.Context, wg *sync.WaitGroup, id int, done chan struct{}) {
	defer wg.Done()
	time.Sleep(time.Duration(rand.Intn(1000)) * time.Millisecond)
	select {
	case <-ctx.Done():
		log.Printf("task %d quit", id)
		return
	case done <- struct{}{}:
		log.Printf("task %d done", id)
	}
}

// concurrentTask 并发的去做任务，谁先做完任务通知其他任务结束，并返回
func concurrentTask() {
	ctx, cancel := context.WithCancel(context.Background())
	defer cancel()
	done := make(chan struct{})
	wg := &sync.WaitGroup{}
	for i := 0; i < gNum; i++ {
		wg.Add(1)
		go func(id int) {
			doTask(ctx, wg, id, done)
		}(i)
	}
	go func() {
		if _, ok := <-done; ok {
			cancel()
		}
	}()
	wg.Wait()
}
func f(n int) int {
	if n <= 2 {
		return n
	}
	return f(n-1) + f(n-2)
}

func f1(n int) int {
	if n <= 1 {
		return n
	}
	a, b := 1, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

func f2(n int) int {
	if n <= 2 {
		return n
	}
	dp := make(map[int]int, n+1)
	dp[0], dp[1] = 1, 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

var dp = make(map[int]int)

func f4(n int) int {
	if n <= 2 {
		return n
	}
	if v, ok := dp[n]; ok {
		return v
	}
	dp[n] = f4(n-1) + f4(n-2)
	return dp[n]
}

func f5(n int, a int, b int) int {
	if n == 0 {
		return a
	}
	return f5(n-1, b, a+b)
}

// 避免for循环反复编译regexp提升性能， 声明全局变量
var (
	reg = regexp.MustCompile(`(aa@qq.com|中国)`)
	re  = "***"
)

// 把符合正则匹配的字符替换成指定字符
func strReplace(old string, new string) string {
	return reg.ReplaceAllString(old, new)
}

// 按字符分割字符串
func strSplit(str string, chunkLen int) []string {
	var res []string
	for i := 0; i < len(str); i += chunkLen {
		end := i + chunkLen
		if end > len(str) {
			end = len(str)
		}
		res = append(res, string([]rune(str)[i:end]))
	}
	return res
}

// 并发把字符串按指定长度分割后替换指定的字符
func replaceStrConcurrently(str string, chunkLen int) string {
	chunks := strSplit(str, chunkLen)
	res := make([]string, len(chunks))
	ch := make(chan struct{})
	for i, chunk := range chunks {
		go func(i int, chunk string) {
			res[i] = strReplace(chunk, re)
			ch <- struct{}{}
		}(i, chunk)
	}
	for range chunks {
		<-ch
	}
	return strings.Join(res, "")
}
